1) Field of the Invention
The present invention relates to a method of and apparatus for determining an optimal solution to a uniform-density layout problem (a layout problem with a density-uniformalization condition), and also relates to a storage medium on which a program for determining the optimal solution is stored.
2) Description of the Related Art
In various fields, a kind of problem is known which requires arranging multiple elements (object elements) under certain conditions (layout conditions) in an optimum state. Such kind of problem is commonly called xe2x80x9ca layout problemxe2x80x9d, xe2x80x9can optimal layout problemxe2x80x9d, xe2x80x9ca layout optimization problemxe2x80x9d, xe2x80x9ca graph-mapping problemxe2x80x9d, and the like (in the following, such kind of problem is referred to simply as xe2x80x9ca layout problemxe2x80x9d for convenience of description. The term xe2x80x9clayout problemxe2x80x9d is used in a common broad meaning for the present, until it is defined strictly later).
To take the above-mentioned LSI-circuits designing as an example, it is required to arrange multiple circuit elements (object elements) on a substrate with meeting the following conditions (layout conditions).
Each of the circuit elements must have a specific size and shape of its own.
The circuit elements must be subjected to a predetermined interconnection relationship.
The circuit elements must be arranged within a specified region on the substrate.
Such requirement is therefore just equivalent to the above-mentioned layout problem.
Other examples of the layout problem include a problem of optimizing delivery routes using trucks, a problem of optimizing operation schedules of factories, a problem of optimizing service diagrams of transport facilities, a problem of optimizing service schedules of nurses, a problem of optimizing Gantt chart (chart showing the relation between working hours and the quantity of production), etc.
A desirable solution to the layout problem is a layout of the object elements that satisfies the layout conditions in as optimum the state as possible. Such a solution is commonly called xe2x80x9ca layout-optimizing solutionxe2x80x9d, xe2x80x9can optimal layout solutionxe2x80x9d, or simply xe2x80x9can optimal solutionxe2x80x9d (in the following, such kind of solution is referred to simply as xe2x80x9can optimal solutionxe2x80x9d for convenience of description. The term xe2x80x9coptimal solutionxe2x80x9d also is used in a common broad meaning for the present, until it is defined strictly later).
A common process of obtaining an optimal solution to a layout problem is to introduce an objective function representing the desirability of a layout solution to the layout conditions and to determine the optimal solution using the objective function.
Specifically, an objective function is formulated so that it increases (or decreases) as desirable the state as it satisfies the layout conditions. And a layout solution that minimizes (or maximizes) the formulated objective function is calculated and determined as the optimal solution.
However, when there are many object elements and the layout conditions are complicated, the objective function is of so high order and so complicated that it is impossible or, even if not so, extremely difficult in practice to calculate exactly the right solution that minimizes (or maximizes) the objective function, because it requires huge operation time.
In such a case, the following technique is commonly used: to improve gradually an initial layout solution to the objective function using an iterative improvement method; to evaluate repeatedly a current layout solution in the improving one after another against specified criteria; and, when there appears any layout solution that satisfies the criteria, to determine the satisfactory layout solution as an approximately optimal solution to the objective function (such a process is often called xe2x80x9coptimization of an objective functionxe2x80x9d). Examples of algorithms used for such optimization include the min-cut algorithm, the n-elements exchanging algorithm, the self-organization algorithm, etc.
To deal with a problem being of a higher order and more complicated, a technique using a so-called genetic algorithm is often used (although such an algorithm is otherwise called by various names, such as an evolutionary programming, and although their strict meanings differ from each other, the term xe2x80x9cgenetic algorithmxe2x80x9d is generically used in a broad meaning throughout the following description). In this technique, various layout solutions being candidates for an optimal solution are expressed as genes, and a group of chromosomes each being a linear string of the genes are generated. Various kinds of operation such as selection, reproduction, crossover, mutation, etc. (genetic operations), are repeatedly performed on the group of chromosomes (population) while the generation of the population is updated. When there appears any gene representing a layout solution that satisfies given criteria, the satisfactory layout solution is determined as an approximately optimal solution to the objective function.
With such techniques as described above, it is possible to obtain, although not a strictly optimal solution objective function that would completely minimize (or maximize) the objective function, an approximately optimal solution that would almost minimize (or maximize) the objective function, with high accuracy enough for practical use.
In the following description, both the process of calculating a strictly optimal solution to a layout problem, as above-described firstly, and the techniques of obtaining any layout solution that satisfies given criteria to determine as an approximately optimal solution to a layout problem, as above-described subsequently, are generically called xe2x80x9cto solve a layout problemxe2x80x9d or xe2x80x9cto search for an optimal solution to a layout problemxe2x80x9d.
In the meantime, there is a kind of layout problem including a condition that the multiple object elements must be distributed in substantially uniform density (hereinafter called a xe2x80x9cdensity-uniformalization conditionxe2x80x9d). The layout problem of this kind is referred to as a xe2x80x9cuniform-density layout problemxe2x80x9d in the following description.
To take the above-mentioned LSI-circuits designing for example again, in addition to the several layout conditions enumerated previously, another condition requiring the multiple object elements to be distributed in substantially uniform density will be demanded actually.
When object elements are numerous and the other layout conditions are much complicated, the density-uniformalization condition is too difficult and too rigid to be satisfied. Consequently, even if any objective function reflecting all the layout conditions including density-uniformalization condition (generic objective function) were formulated, the order of such an objective function would be excessive, so that it is quite difficult to search for an optimal solution to the objective function.
Thus the following technique has been taken conventionally in order to search for an optimal solution to the uniform-density layout problem: generating an objective function based on the remaining layout conditions other than the density-uniformalization condition; searching for a provisional optimal solution using the generated objective function; and improving the provisional optimal solution by executing an algorithm of some kind for reducing non-uniformity in density of the multiple object elements. Examples of such conventional non-uniformity reducing algorithm include the ones that the inventors proposed previously (Japanese Patent Laid-Open Publication No. HEI 11-134315 and Japanese Patent Laid-Open Publication No. 2000-90065), the one disclosed in REN-SONG TSAY et al., xe2x80x9cPROUD: A SEA-OF-GATES PLACEMENT ALGORITHMxe2x80x9d (IEEE DESIGN and TEST OF COMPUTERS, 1988), etc.
However, when solving a uniform-density layout problem by the above-mentioned conventional technique, huge arithmetic processing will be needed for executing the non-uniformity reducing algorithm in addition to the optimization of the objective function relating to the other layout conditions, so that it will take very long time to search for the optimal solution.
As the LSI design technology and other various technologies are growing more developed and more complicated in recent years, it is expected that such layout problems as to require the search of an optimal solution under a density-uniformalization condition will be more increased and more complicated from now on. Against this backdrop, it is desired to develop a technology for determining an optimal solution to a uniform-density layout problem more efficiently and with a higher speed, even if the object elements are numerous and the layout conditions are extremely complicated.
With the foregoing problems in view, it is an object of the present invention to provide a method of and apparatus for determining more efficiently an optimal solution to a uniform-density layout problem with high speed, even if the object elements are numerous and the layout conditions are quite complicated.
In addition, another object of the present invention is to provide a storage medium storing a program for making a computer to execute the method for determining an optimal solution.
According to an aspect of the present invention, there is provided a computer-implemented method of determining a first optimal solution to a first layout problem requiring an optimal layout of a multiplicity of elements in a predetermined region under a first set of conditions, which includes a uniformalization condition such that the multiple elements are distributed in substantially uniform density throughout the predetermined region, as the first optimal solution, wherein said first layout problem is analyzable into the uniformalization condition and a second layout problem requiring an optimal layout of the multiple elements in the same predetermined region under a second set of conditions, which consists of the remaining conditions of the first set of conditions other than the uniformalization condition, as a second optimal solution, comprising the steps of: (A) generating a linear combination of a first objective function, which represents the second set of conditions of said second layout problem, and a second objective function, which represents the uniformalization condition of said first layout problem, as a third objective function, which is assumed to represent the first set of conditions of said first layout problem; and (B) optimizing said third objective function generated in said step (A), whereby the first optimal solution to the first layout problem is determined.
According to another aspect of the present invention, there is provided a computer-implemented method of determining a first optimal solution to the first layout problem, comprising the steps of: (a) obtaining an initial layout of the multiple elements in the predetermined region; (b) generating a linear combination of a first objective function, which represents the second set of conditions of said second layout problem, and a second objective function, which represents the uniformalization condition of said first layout problem, as a third objective function, which is assumed to represent the first set of conditions of said first layout problem; and (c) optimizing the third objective function generated in said step (b) by executing an iterative-improvement algorithm on said third objective function using said initial layout obtained in said step (a) as an initial solution, whereby the first optimal solution to the first layout problem is determined.
As a preferable feature of the present invention, said method further comprises the step of (d) representing at least one of a group of one or more first parameters, which relate to said generating of said third objective function in said step (b), and a group of one or more second parameters, which relate to said executing of said iterative-improvement algorithm in said step (c), as genes and executing a genetic algorithm on an initial population of individuals each of which has at least one chromosome being a string of the genes; and at least one of said generating of said third objective function in said step (b) and said executing of said iterative-improvement algorithm in said step (c) is carried out based on parameters represented by genes included in chromosomes of the individuals in the resultant population from said executing of said genetic algorithm in said step (d).
As another preferable feature, said generating of said third objective function in said step (b), said executing of said iterative-improvement algorithm in said step (c) and, as the case may be, said executing of said genetic algorithm in said step (d) are repeatedly carried out according to a predetermined schedule.
As still another preferable feature, in said step (a), said second optimal solution to said second objective function is determined and obtained as said initial layout.
As a further preferable feature, in said step (B) or (b), at least one of a function relating to density of the multiple elements, a function relating to area density of the multiple elements, a function relating to the number of overlaps between any two or more of the multiple elements and a function relating to the total area of overlaps between any two or more of the multiple elements is generated as said second objective function.
As a still further preferable feature, said step (b) includes: making a virtual layout of the multiple elements in the predetermined region, based on a current actual layout of the multiple elements in the predetermined region, in such a manner that the multiple elements are distributed in substantially uniform density throughout the predetermined region; and generating a function which represents a relationship between said virtual layout of the multiple elements and said current actual layout of the multiple elements as said second objective function.
In the last case, it is preferable that in said step (b), the multiple elements are virtually disposed next to one another with respect to one of 1) a vertex of the predetermined region, 2) a side of the predetermined region, 3) a center of the predetermined region or 4) an alternately selected one of vertices of the predetermined region, so as to arrange the multiple elements in said virtual layout.
As an additional preferable feature, in said step (b), if the predetermined region has any local subregion in which an actual layout of the multiple elements is to be prohibited, the multiple elements are skipped over said local subregion while the multiple elements are arranged in the predetermined region in said virtual layout. And if any one of the multiple elements is placed in a virtual position to overlap said local subregion while the multiple elements are arranged in said virtual layout, said virtual position of said one element is shifted outwardly off said local subregion in such a direction 1) that a distance between a current actual position of said one element and the shifted virtual position of said one element is minimal, 2) that a distance between an outline of the local subregion and an outline of the predetermined region is maximal, or 3) that a distance of shifting of said virtual position of said one element is minimal.
As a still additional preferable feature, in said step (b), the multiple elements are arranged in said virtual layout 1) based on said initial layout of the multiple elements obtained in said step (a), 2) at each of one or more scheduled occasions in accordance with said predetermined schedule, based on said current actual layout of the multiple elements in said step (c) for each of the occasions, or 3) at each of one or more random occasions, based on said current actual layout of the multiple elements in said step (c) for each of the occasions.
As an further additional preferable feature, in said step (b), said generating of a new third objective function is carried out at each of a plurality of scheduled occasions in accordance with said predetermined schedule, while at least one of 1) a coefficient of said linear combination of said first and second objective functions and 2) a definition of said second objective function varies for each of the occasions.
As a still further additional preferable feature, in said step (d), at least either of 1) one or more coefficients of said third objective function generated in said step (b) and 2) parameters of said predetermined schedule are represented by genes, and the chromosome of each individual is generated using said genes.
In the former case, it is preferable that 1) in said step (d), assuming that said third objective function generated in said step (b) is expressed as Cost+xcex1U where Cost is said first objective function and U is said second objective function, the coefficient xcex1 is represented by said genes, and that 2) assuming that said third objective function generated in said step (b) is expressed as (Costx+xcex1xUx)+(Costy+xcex1yUy) where Costx is an x-coordinate component of said first objective function, Costy is a y-coordinate component of said first objective function, Ux is an x-coordinate component of said second objective function, and Uy is a y-coordinate component of said second objective function, the coefficient xcex1x and the coefficient xcex1y are represented by said genes.
It is also preferable that 1) in said step (d), assuming that said third objective function generated in said step (b) is expressed as Cost+xcex1U where Cost is said first objective function and U is said second objective function, and that xcex1 is a function of a current iteration count of said iterative-improvement algorithm with coefficients xcex21, xcex22, . . . , xcex2n, the coefficients xcex21, xcex22, . . . , xcex2n are represented by said genes, and that 2) assuming that said third objective function generated in said step (b) is expressed as (Costx+xcex1xUx)+(Costy+xcex1yUy) where Costx is an x-coordinate component of said first objective function, Costy is a y-coordinate component of said first objective function, Ux is an x-coordinate component of said second objective function, Uy is a y-coordinate component of said second objective function, xcex1x is a function of a current iteration count of said iterative-improvement algorithm with coefficients xcex2x1, xcex2x2, . . . , xcex2xn, and xcex1y is a function of a current iteration count of said iterative-improvement algorithm with coefficients xcex2y1, xcex2y2, . . . , xcex2yn, the coefficients xcex2x1, xcex2x2, . . . , xcex2xn and the coefficients xcex2y1, xcex2y2, . . . , xcex2yn are represented by said genes.
As a still further additional preferable feature, said step (d) includes performing an exchanging crossover, or a weighting crossover based on a weighted average of gene values of the two individuals of said pair, as a genetic operation on at least one pair of individuals in the population.
As a still further additional preferable feature, said step (d) includes performing a mutation as a genetic operation on at least one individual in the population by varying a gene value of the one individual at random within a predetermined range or, when a resultant layout of the multiple elements from a previous execution of said iterative-improvement algorithm in said step (c) does not meet a predetermined criterion, by varying a gene value of the one individual within such a range that the layout of the multiple elements is improved.
As a still further additional preferable feature, said step (d) includes: evaluating a fitness of each of individuals of a current population based on a result of a previous execution of said iterative-improvement algorithm in said step (c); selecting a number of individuals from the individuals of the current population based on the evaluated fitness of each said individual to thereby generate a new population; and executing said genetic algorithm on the generated new generation. In this case, it is preferable that said evaluating in said step (d) calculates a fitness value for each said individual using said first objective function and evaluates the fitness of each said individual based on the calculated fitness value.
As a still further additional preferable feature, said step (d) includes: dividing individuals of a current population into a plurality of subpopulations in accordance with a kind of genes included in a chromosome of each of the individuals of the current population; executing said genetic algorithm on each of the plural subpopulations separately; and during said executing said genetic algorithm, exchanging a number of individuals between the plural subpopulations in accordance with said predetermined schedule.
Specifically, it is preferable that in said step (d), the individuals of the current population is divided into 1) a first subpopulation of individuals, each of which has genes representing parameters of said third objective function generated in said step (b), 2) a second subpopulation of individuals, each of which has genes representing parameters of said predetermined schedule, and 3) a third subpopulation of individuals, each of which has both genes representing parameters of said third objective function generated in said step (b) and genes representing parameters of said predetermined schedule.
In this case, it is preferable that 1) said step (d) includes: selecting one individual from the first subpopulation and another individual from the second subpopulation as parents; performing a crossover operation on a pair of chromosomes of the parents to thereby generate a pair of chromosomes for children; and migrating a pair of children, each of which has a respective one of the generated chromosome pair, into the third subpopulation, and 2) that said step (d) includes: selecting one individual from the first or second subpopulation and another individual from the third subpopulation as parents; performing a crossover operation on a pair of chromosomes of the parents to thereby generate a pair of chromosomes for children; and migrating a pair of children, each of which has a respective one of the generated chromosome pair, into the first or second subpopulation and the third subpopulation respectively.
According to still another aspect of the present invention, there is provided an apparatus for determining a first optimal solution to the first layout problem, comprising: an objective-function generating section for generating a linear combination of a first objective function, which represents the second set of conditions of the formulated second layout problem, and a second objective function, which represents the uniformalization condition of the first layout problem, as a third objective function, which is assumed to represent the first set of conditions of the first layout problem; and an objective-function optimizing section for optimizing the third objective function generated by said objective-function generating section, thereby determining the first optimal solution to the first layout problem.
According to a further aspect of the present invention, there is provided an apparatus for determining a first optimal solution to the first layout problem, comprising: an initial-layout obtaining section for obtaining an initial layout of the multiple elements in the predetermined region; an objective-function generating section for generating a linear combination of a first objective function, which represents the second set of conditions of the formulated second layout problem, and a second objective function, which represents the uniformalization condition of the first layout problem, as a third objective function, which is assumed to represent the first set of conditions of the first layout problem; and an iterative-improvement-algorithm executing section for optimizing the third objective function generated in said objective-function generating section by executing an iterative-improvement algorithm on the third objective function using the initial layout obtained in said initial-layout obtaining section as an initial solution, thereby determining the first optimal solution to the first layout problem.
As a preferable feature of the present invention, said apparatus further comprises a genetic-algorithm executing section for representing at least one of a group of one or more first parameters, which relate to the generating of the third objective function in said objective-function generating section, and a group of one or more second parameters, which relate to the executing of the iterative-improvement algorithm in said iterative-improvement-algorithm executing section, as genes and for executing a genetic algorithm on an initial population of individuals each of which has at least one chromosome being a string of the genes; wherein at least one of the generating of the third objective function in said objective-function generating section and the executing of the iterative-improvement algorithm in said iterative-improvement-algorithm executing section is carried out based on parameters represented by genes included in chromosomes of the individuals in the resultant population from the executing of the genetic algorithm in said genetic-algorithm executing section.
As another preferable feature of the present invention, said apparatus further comprises a schedule management section for preparing a schedule relating to the generation of the third objective function by said objective-function generating section, the execution of the iterative-improvement algorithm by said iterative-improvement-algorithm executing section and, as the case may be, the execution of the genetic algorithm by said genetic-algorithm executing section, and for controlling said objective-function generating section, said iterative-improvement-algorithm executing section and said genetic-algorithm executing section to iteratively carry out the generation of the third objective function, the execution of the iterative-improvement algorithm and the execution of the genetic algorithm according to the prepared schedule.
According to a still further aspect of the present invention, there is provided a computer-readable storage medium storing a computer program for determining a first optimal solution to the first layout problem, wherein said program instructs a computer to carry out the procedures corresponding to the steps of the method of the present invention:
With the foregoing features of the method, apparatus and medium according to the present invention, it is possible to guarantee the following advantageous results.
(1) Since an optimal solution to a given uniform-density layout problem can be searched for using only a single objective function being relatively simple and of low order (third objective function), it is possible to determine efficiently the optimal solution with high speed, without the need of any special procedure for reducing non-uniformity in density of the multiple object elements.
(2) Even if the object elements are numerous and the layout conditions are complicated, since an optimal solution to a given uniform-density layout problem can be searched for by iteratively improving an initial solution through the optimization of a simple objective function being of relatively low order (third objective function), it is possible to determine efficiently the optimal solution with high speed, without the need of any special procedure for reducing non-uniformity in density of the multiple object elements.
(3) Even if the object elements are still more numerous and the layout conditions are quite complicated, it is possible to appropriately determine various parameters necessary for generating the third objective function and/or executing the iterative-improvement algorithm objective function with high speed by executing a genetic algorithm according to details of the uniform-density layout problem, so that the speed of and the efficiency in determining the optimal solution is further improved.
(4) Since an appropriate third objective function is newly generated occasionally in accordance with the progress of the iterative improvement, it is possible to improve the speed of and the efficiency in determining the optimal solution.
(5) Since a layout appropriately reflecting the remaining layout conditions other than the density-uniformalization condition is obtained and used as an initial layout for the search of the optimal solution to the uniform-density layout problem, it is possible to improve the speed of and the efficiency in determining the optimal solution.
(6) Since a relatively simple function (second objective function) appropriately representing the density-uniformalization condition is used, it is possible to generate an appropriate objective function (third objective function) representing the uniform-density layout problem with high speed, so that the speed of and the efficiency in determining the optimal solution is further improved.
(7) Since parameters relating to objective function (third objective function) and parameters relating to the execution of each step are determined appropriately with high speed in accordance with the features of the uniform-density layout problem, it is possible to improve the speed of and the efficiency in determining the optimal solution.
(8) Since the appropriate parameters are determined effectively by evaluating the fitness value of each chromosome, it is possible to generate an appropriate objective function (third objective function) representing the uniform-density layout problem with high speed, so that the speed of and the efficiency in determining the optimal solution is further improved.
(9) Since the appropriate parameters are determined effectively based on a great diversity of chromosomes, it is possible to generate an appropriate objective function (third objective function) representing the uniform-density layout problem with high speed, so that the speed of and the efficiency in determining the optimal solution is further improved.
(10) Since a computer-readable storage medium is provided which stores a computer program instructing a computer to carry out the method of the present invention, it is possible to carry out the present method in various environments, so that the present invention can be applied to solve uniform-density layout problems in diverse situations.